package 简单.模拟;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 给你一个字符串 s 和一个字符 c ，且 c 是 s 中出现过的字符。
 * 返回一个整数数组 answer ，其中 answer.length == s.length 且 answer[i] 是 s 中从下标 i 到离它 最近 的字符 c 的 距离 。
 * 两个下标 i 和 j 之间的 距离 为 abs(i - j) ，其中 abs 是绝对值函数。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/shortest-distance-to-a-character
 */
public class 字符的最短距离_821 {

    public static void main(String[] args) {

        System.out.println(Arrays.toString(shortestToChar2("loveleetcode", 'e')));

    }

    /**
     * 先遍历得到c字符所在所有索引
     * 二分查找每个位置和c字符相隔的最短距离
     *
     * @param s
     * @param c
     * @return
     */
    public static int[] shortestToChar(String s, char c) {
        int[] ans = new int[s.length()];
        List<Integer> cList = new ArrayList<>();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == c) {
                cList.add(i);
            }
        }
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) != c) {
                ans[i] = search(cList, i);
            }
        }
        return ans;
    }

    //  二分查找
    public static int search(List<Integer> list, int i) {
        int left = 0, right = list.size() - 1;
        int min = 10000;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int cur = list.get(mid);
            if (cur == i) {
                return 0;
            } else if (cur < i) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
            min = Math.min(min, Math.abs(cur - i));
        }
        return min;
    }

    /**
     * 两次遍历
     * 对于每个字符求最短路径
     * 左边的c的距离
     * 右边的c的距离，取较小值
     *
     * @param s
     * @param c
     * @return
     */
    public static int[] shortestToChar2(String s, char c) {
        int[] ans = new int[s.length()];

        Integer leftC = null;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == c) {
                leftC = i;
            } else if (leftC != null) {
                ans[i] = Math.abs(i - leftC);
            }
        }

        Integer rightC = null;
        for (int i = s.length() - 1; i >= 0; i--) {
            if (s.charAt(i) == c) {
                rightC = i;
            } else if (rightC != null) {  // 开头的右边的c的距离是0是不合理的
                ans[i] = ans[i] != 0 ? Math.min(ans[i], Math.abs(i - rightC))
                        : Math.abs(i - rightC);
            }
        }
        return ans;
    }
}
